ff1588d761d55f48f61a52249e1dcc24

<!DOCTYPE html>

<title>Forward-Algorithmus</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Forward-Algorithmus</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Der <b>Forward-Algorithmus</b> (auch <i>Vorwärts-Algorithmus</i>, <i>Vorwärts-Prozedur</i>) berechnet mit Hilfe sogenannter <b>Forward-Variablen</b> für ein gegebenes <a href="Hidden-Markov-Modell" class="mw-redirect" title="Hidden-Markov-Modell">Hidden-Markov-Modell</a> die <a href="Wahrscheinlichkeit" title="Wahrscheinlichkeit">Wahrscheinlichkeit</a> einer bestimmten Beobachtung.

Er verwendet die Programmiermethode der <a href="Dynamische_Programmierung" title="Dynamische Programmierung">dynamischen Programmierung</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Markov-Modell">Markov-Modell</h2></div>

<p>Das Markov-Modell ist definiert als <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda =(S;V;A;B;\pi )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda =(S;V;A;B;\pi )}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2c0a1e063a0203eeba91649504852be8cd859748.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.524ex; height:2.843ex;" alt="{\displaystyle \lambda =(S;V;A;B;\pi )}" loading="lazy"></span>, wobei

</p>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> die Menge der verborgenen Zustände,</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"></span> das <a href="Alphabet_(Informatik)" title="Alphabet (Informatik)">Alphabet</a> der beobachtbaren Symbole,</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> die Matrix der <a href="%C3%9Cbergangswahrscheinlichkeit" class="mw-redirect" title="Übergangswahrscheinlichkeit">Übergangswahrscheinlichkeiten</a>,</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span> die Matrix der Emissionswahrscheinlichkeiten,</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9be4ba0bb8df3af72e90a0535fabcc17431e540a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.332ex; height:1.676ex;" alt="{\displaystyle \pi }" loading="lazy"></span> die Anfangsverteilung für die möglichen Anfangszustände,</li></ul>

<p>bezeichnet.

</p>

<div class="mw-heading mw-heading2"><h2 id="Aufgabenstellung_und_Forward-Variablen">Aufgabenstellung und Forward-Variablen</h2></div>

<p>Gegeben sei ein <a href="Wort_(Theoretische_Informatik)" class="mw-redirect" title="Wort (Theoretische Informatik)">Wort</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {o}}=o_{1}o_{2}\dots o_{T}\in V^{*}}">

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {o}}=o_{1}o_{2}\dots o_{T}\in V^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b5e6941a5773976db57f6601f589e8691a6f7f5e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:20.648ex; height:2.676ex;" alt="{\displaystyle {\boldsymbol {o}}=o_{1}o_{2}\dots o_{T}\in V^{*}}" loading="lazy"></span>. Der Forward-Algorithmus berechnet nun <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P({\boldsymbol {o}}|\lambda )}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P({\boldsymbol {o}}|\lambda )}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/778bda8a7a5c8f76557ea67236098d9364ed6ef7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.917ex; height:2.843ex;" alt="{\displaystyle P({\boldsymbol {o}}|\lambda )}" loading="lazy"></span>, also die Wahrscheinlichkeit im vorhandenen Modell <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b43d0ea3c9c025af1be9128e62a18fa74bedda2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.355ex; height:2.176ex;" alt="{\displaystyle \lambda }" loading="lazy"></span> tatsächlich die Beobachtung <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {o}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {o}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/516a3553708e67304ca0f2f35e765f5e8b84bc2b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.36ex; height:1.676ex;" alt="{\displaystyle {\boldsymbol {o}}}" loading="lazy"></span> zu machen.

</p><p>Dafür werden die <i>Forward-Variablen</i> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{t}(i)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{t}(i)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bdaa1fe0153678fe0e2401b3a32a8c903b30f304.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.925ex; height:2.843ex;" alt="{\displaystyle \alpha _{t}(i)}" loading="lazy"></span> verwendet. Darin ist die Wahrscheinlichkeit zum Zeitpunkt <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq t\leq T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq t\leq T}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/234966dc61d2f4dca4cb2efd5ca4d5737ec0c991.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.835ex; height:2.343ex;" alt="{\displaystyle 1\leq t\leq T}" loading="lazy"></span> das <a href="Wort_(Theoretische_Informatik)#Präfix" class="mw-redirect" title="Wort (Theoretische Informatik)">Präfix</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle o_{1}o_{2}\ldots o_{t}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle o_{1}o_{2}\ldots o_{t}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/da6738e71cfebf74eed3f3fd5d70b49cdd0924b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.815ex; height:2.009ex;" alt="{\displaystyle o_{1}o_{2}\ldots o_{t}}" loading="lazy"></span> beobachtet zu haben und im Zustand <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{i}\in S}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{i}\in S}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87a8178559b9f271a78c8287257e81fd924faef5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.23ex; height:2.509ex;" alt="{\displaystyle s_{i}\in S}" loading="lazy"></span> zu sein gespeichert:

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{t}(i)=P(o_{1}o_{2}\ldots o_{t};q_{t}=s_{i}|\lambda )}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6bd90d27319048b766c06650389c183f29d7e8db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.281ex; height:2.843ex;" alt="{\displaystyle \alpha _{t}(i)=P(o_{1}o_{2}\ldots o_{t};q_{t}=s_{i}|\lambda )}" loading="lazy"></span></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Funktionsweise">Funktionsweise</h2></div>

<p>Die Forward-Variablen, und damit auch die Gesamtwahrscheinlichkeit, lassen sich rekursiv berechnen:

</p>

<dl><dt>Initialisierung</dt>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{1}(i)=\pi _{i}\cdot b_{i}(o_{1}),\qquad 1\leq i\leq \left|S\right|}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3cb7254ee1ddf8dc2eaccb1ed41c95542faad8ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.478ex; height:2.843ex;" alt="{\displaystyle \alpha _{1}(i)=\pi _{i}\cdot b_{i}(o_{1}),\qquad 1\leq i\leq \left|S\right|}" loading="lazy"></span></dd></dl>

<dl><dt>Rekursion</dt>

<msub>

</mrow>

</msub>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{t}(i)=\left(\sum _{j=1}^{|S|}\alpha _{t-1}(j)a_{ji}\right)\cdot b_{i}(o_{t});\qquad 1<t\leq T,\ 1\leq i\leq \left|S\right|}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/df93f2459180663af7abd51dde39d46759e49ab9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:60.659ex; height:8.009ex;" alt="{\displaystyle \alpha _{t}(i)=\left(\sum _{j=1}^{|S|}\alpha _{t-1}(j)a_{ji}\right)\cdot b_{i}(o_{t});\qquad 1<t\leq T,\ 1\leq i\leq \left|S\right|}" loading="lazy"></span></dd></dl>

<dl><dt>Terminierung</dt>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P({\boldsymbol {o}}|\lambda )=\sum _{j=1}^{|S|}\alpha _{T}(j)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f36c2c18521fb7fc256f5c3dcea1be2c972a2170.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:19.401ex; height:8.009ex;" alt="{\displaystyle P({\boldsymbol {o}}|\lambda )=\sum _{j=1}^{|S|}\alpha _{T}(j)}" loading="lazy"></span></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Komplexität"><span id="Komplexit.C3.A4t"></span>Komplexität</h2></div>

<p>Der Algorithmus benötigt <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|S|^{2}\cdot T)}">

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|S|^{2}\cdot T)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5fcfc23441a169454e26857e90be8e64b0d77065.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.745ex; height:3.343ex;" alt="{\displaystyle O(|S|^{2}\cdot T)}" loading="lazy"></span> Operationen und bietet ein effizientes Verfahren zur Berechnung der gesuchten Wahrscheinlichkeit.

Der Speicherbedarf liegt in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|S|\cdot T)}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|S|\cdot T)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/23903747f743a28d8b57afcc499e6e91be145e3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.691ex; height:2.843ex;" alt="{\displaystyle O(|S|\cdot T)}" loading="lazy"></span>, da zur Erreichung der polynomiellen Laufzeit alle <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{t}(i)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{t}(i)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bdaa1fe0153678fe0e2401b3a32a8c903b30f304.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.925ex; height:2.843ex;" alt="{\displaystyle \alpha _{t}(i)}" loading="lazy"></span> in einer <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |S|\times T}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |S|\times T}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/395802659b3f9276ac8edfd9b7475e7c12cd42b5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.27ex; height:2.843ex;" alt="{\displaystyle |S|\times T}" loading="lazy"></span> Matrix abgelegt werden.

</p><p>Wenn die Zwischenergebnisse von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{t}(i)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{t}(i)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bdaa1fe0153678fe0e2401b3a32a8c903b30f304.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.925ex; height:2.843ex;" alt="{\displaystyle \alpha _{t}(i)}" loading="lazy"></span> für <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t<T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t<T}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/208d09df932e2c28141f79503da2eaaa5a4ba13f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.574ex; height:2.176ex;" alt="{\displaystyle t<T}" loading="lazy"></span> nach der Beendigung der Rekursion nicht benötigt werden, dann reduziert sich der Speicherbedarf auf <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|S|)}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|S|)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47a605795e87b54fd697a78fd16c2e9517e3db01.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.376ex; height:2.843ex;" alt="{\displaystyle O(|S|)}" loading="lazy"></span>, da zwei Spaltenvektoren der Länge <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |S|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |S|}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/28d901e98a035ff4c0e37fe6dd8e750ece6c1f0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.793ex; height:2.843ex;" alt="{\displaystyle |S|}" loading="lazy"></span> ausreichen um <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{t-1}(i)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{t-1}(i)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d7c9697ef124c90fc3a2eb8923ade6bb2ee3e952.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.026ex; height:2.843ex;" alt="{\displaystyle \alpha _{t-1}(i)}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{t}(i)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{t}(i)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bdaa1fe0153678fe0e2401b3a32a8c903b30f304.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.925ex; height:2.843ex;" alt="{\displaystyle \alpha _{t}(i)}" loading="lazy"></span> in jedem Rekursionsschritt zu speichern.

</p>

<div class="mw-heading mw-heading2"><h2 id="Weitere_Anwendungen">Weitere Anwendungen</h2></div>

<p>Die Forward-Variablen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{t}(i)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{t}(i)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bdaa1fe0153678fe0e2401b3a32a8c903b30f304.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.925ex; height:2.843ex;" alt="{\displaystyle \alpha _{t}(i)}" loading="lazy"></span> werden zusammen mit den <i><a href="Backward-Algorithmus#Aufgabenstellung_und_Backward-Variablen" title="Backward-Algorithmus">Backward-Variablen</a></i> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \beta _{t}(i)=P(o_{t+1}\dots o_{T}|q_{t}=s_{i};\lambda )}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \beta _{t}(i)=P(o_{t+1}\dots o_{T}|q_{t}=s_{i};\lambda )}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/04f6a336aff0c6ed586175262155db95917c03cb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.363ex; height:2.843ex;" alt="{\displaystyle \beta _{t}(i)=P(o_{t+1}\dots o_{T}|q_{t}=s_{i};\lambda )}" loading="lazy"></span> für den <a href="Baum-Welch-Algorithmus" title="Baum-Welch-Algorithmus">Baum-Welch-Algorithmus</a> zur Lösung des mit Hidden-Markov-Modellen gegebenen Lernproblems benötigt.

</p><p>Außerdem ermöglicht deren Kenntnis die Bestimmung der Wahrscheinlichkeit, bei der Beobachtung von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {o}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {o}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/516a3553708e67304ca0f2f35e765f5e8b84bc2b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.36ex; height:1.676ex;" alt="{\displaystyle {\boldsymbol {o}}}" loading="lazy"></span> zu einem <i>festen</i> Zeitpunkt <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"></span> im Zustand <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cfda82668232cbdc0874ed28ab8b6079420d1ffe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.89ex; height:2.009ex;" alt="{\displaystyle s_{i}}" loading="lazy"></span> gewesen zu sein, denn nach dem <a href="Satz_von_Bayes" title="Satz von Bayes">Satz von Bayes</a> gilt:

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(q_{t}=s_{i}|{\boldsymbol {o}};\lambda )={\frac {\alpha _{t}(i)\cdot \beta _{t}(i)}{P({\boldsymbol {o}}|\lambda )}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bded085071f6281655a4d47c46bdae02b31b8730.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:30.095ex; height:6.509ex;" alt="{\displaystyle P(q_{t}=s_{i}|{\boldsymbol {o}};\lambda )={\frac {\alpha _{t}(i)\cdot \beta _{t}(i)}{P({\boldsymbol {o}}|\lambda )}}}" loading="lazy"></span></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Backward-Algorithmus" title="Backward-Algorithmus">Backward-Algorithmus</a></li>

<li><a href="Viterbi-Algorithmus" title="Viterbi-Algorithmus">Viterbi-Algorithmus</a></li>

<li><a href="Baum-Welch-Algorithmus" title="Baum-Welch-Algorithmus">Baum-Welch-Algorithmus</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>R. Durbin et al.: <cite style="font-style:italic">Biological sequence analysis. Probabilistic models of proteins and nucleic acids. <i>11th printing, corrected 10. reprinting</i></cite>. Cambridge University Press, Cambridge u. a. 2006, ISBN 0-521-62971-3, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>59</span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Forward-Algorithmus&rft.au=R.+Durbin+et+al.&rft.btitle=Biological+sequence+analysis.+Probabilistic+models+of+proteins+and+nucleic+acids.+11th+printing%2C+corrected+10.+reprinting&rft.date=2006&rft.genre=book&rft.isbn=0521629713&rft.pages=59&rft.place=Cambridge+u.+a.&rft.pub=Cambridge+University+Press" style="display:none"> </span></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li>E. G. Schukat-Talamazzini: <a rel="nofollow" class="external text" href="https://www.minet.uni-jena.de//fakultaet/schukat/MAS/Scriptum/lect05-HMM.pdf"><i>Spezielle Musteranalysesysteme</i></a> (PDF, 1,3 MB) Vorlesung im WS 2012/13 an der Universität Jena. Kapitel 5 Folie 32ff.</li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2021-01-13" href="https://de.wikipedia.org/wiki/?title=Forward-Algorithmus&oldid=207603695">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>